package thread.puzzle;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

// 串行解答
public class SequentialPuzzleSolver <P, M> {
    private final Puzzle<P, M> puzzle;
    private final Set<P> seen = new HashSet<P>();
    public SequentialPuzzleSolver(Puzzle<P, M> puzzle) {
        this.puzzle = puzzle;
    }

    public List<M> solve() {
        P pos = puzzle.initialPosition();
        return search(new PuzzleNode<P, M>(pos, null, null));
    }

    // 经过合法的点 走到终点
    private List<M> search(PuzzleNode<P, M> node) {
        if (!seen.contains(node.pos)) {
            // 添加当前路径
            seen.add(node.pos);
            // 如果是目标点 返回当前list = while {add(node.pre); node=node.pre;}
            if (puzzle.isGoal(node.pos))
                return node.asMoveList();
            // 遍历合法move移动规则集合
            for (M move : puzzle.legalMoves(node.pos)) {
                // 通过移动规则移动到下一个点
                P pos = puzzle.move(node.pos, move);
                // 当前点 移动规则 上一个节点
                PuzzleNode<P, M> child = new PuzzleNode<P, M>(pos, move, node);
                // 深搜
                List<M> result = search(child);
                if (result != null)
                    return result;
            }
        }
        return null;
    }
}
